In the field of graphics processing, computational geometry is a critical discipline used to represent objects and object motion (via simulation). In addition to computer graphics and computer-aided design and manufacturing, other applications of computational geometry include the fields of robotics, geographic information systems (GIS), integrated circuit design, computer-aided engineering (CAE), and computer vision. One aspect common to almost every application of computational geometry is the detection of object collisions, particularly in physics simulations.
A central challenge facing these applications is to perform this detection as efficiently as possible, with good scaling behavior, and without requiring any more data than necessary. Two popular approaches to this challenge may be characterized as Linear Programming, and Convex Proximity Algorithms.
With respect to linear programming approaches, the computing resources (e.g., memory space and time) required to perform typical approaches scale exponentially with the number of elements, which can be prohibitive when the number of elements becomes large. Moreover, linear programming solutions typically are completely incapable handling input sets of an infinite or indefinite size. With respect to Convex Proximity Algorithms, these approaches are typically limited to two convex shapes. For convex polytopes with a finite number of faces, additional boundary data must be determined (and thus calculated), thereby requiring inefficient extra processing (or memory) overhead before the process can even be performed.